Хаос в цепочке поставок 📉
Корабли прибывают в случайном порядке. Нам нужно вычислить показатель хаоса (количество инверсий), чтобы оптимизировать ИИ-систему управления движением.
Что такое инверсия?
Пара индексов $(i, j)$ является инверсией, если:
- $i < j$ (корабль $i$ прибывает раньше, чем $j$)
- $A[i] > A[j]$ (у корабля $i$ более высокий идентификатор приоритета)
Анализ 🔍
Пример последовательности: [2, 4, 1, 3, 5]
- ❌ (2, 1): 2 прибывает раньше 1, но 2 > 1
- ❌ (4, 1): 4 прибывает раньше 1, но 4 > 1
- ❌ (4, 3): 4 прибывает раньше 3, но 4 > 3
- Общий хаос: 3 инверсии
Вызов
Прямой двойной цикл имеет сложность $O(N^2)$.
for i in range(n):
for j in range(i+1, n): ...
for j in range(i+1, n): ...
Для $N=100 ext{,}000$ это займёт около 10 миллиардов операций. Результат: превышено время выполнения.